#include <stdio.h>
#include <string.h>

#define MAXLINES 5000		/* max #lines to be sorted */
#define MAXBUFSIZE 1000		

char *lineptr[MAXLINES];	/* pointers to text lines */

int readlines_1(char *lineptr[], int nlines, char *buf, size_t *bufp);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

// sort input lines
int main()
{
	int nlines;	// number of input lines read
	char buf[MAXBUFSIZE];
	size_t bufp = 0;

	if((nlines = readlines_1(lineptr, MAXLINES, buf, &bufp)) >= 0)
	{
		qsort(lineptr, 0, nlines - 1);
		printf("\n");
		writelines(lineptr, nlines);
		return 0;
	}
	else 
	{
		printf("error: input too big to sort\n");
		return 1;
	}
}

#define MAXLEN 1000	// max length of any input line

int Getline(char *, int);
char *alloc(int);

// readlines: read input lines
int readlines_1(char *lineptr[], int maxlines, char *buf, size_t *bufp) 
{
	int len, nlines;
	char line[MAXLEN];
	size_t *p = bufp;

	nlines = 0;
	while((len = Getline(line, MAXLEN)) > 0)
		if(nlines >= maxlines || *p + len >= MAXBUFSIZE)
			return -1;
		else
		{
			line[len - 1] = '\0';		// delete newline
			strcpy(&buf[*p], line);
			lineptr[nlines++] = &buf[*p];
			*p += len;
		}
	return nlines;
}

// writelines: write output lines
void writelines(char *lineptr[], int nlines)
{
	int i;
	for(i = 0; i < nlines; i++)
		printf("%s\n", lineptr[i]);
}

// Getline: get line into s, return length
int Getline(char s[], int lim)
{
	int c, i;

	i = 0;
	while(--lim > 0 && (c = getchar()) != EOF && c != '\n')
		s[i++] = c;
	if(c == '\n')
		s[i++] = c;
	s[i] = '\0';
	return i;
}

// qsort: sort v[left] ... v[right] into increasing order
void qsort(char *v[], int left, int right)
{
	int i, last;
	void swap(char *v[], int i, int j);

	if(left >= right)		// do nothing if array contains
		return;			// fewer than two elements
	swap(v, left, (left + right) / 2);
	last = left;
	for(i = left + 1; i <= right; i++)
		if(strcmp(v[i], v[left]) < 0)
			swap(v, ++last, i);
	swap(v, left, last);
	qsort(v, left, last - 1);
	qsort(v, last + 1, right);
}

// swap: interchange v[i] and v[j]
void swap(char *v[], int i, int j)
{
	char *temp;
	temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}
